// @algorithm @lc id=1029 lang=cpp 
// @title vertical-order-traversal-of-a-binary-tree


// #define print(...)
// @test([3,9,20,null,null,15,7])=[[9],[3,15],[20],[7]]
// @test([1,2,3,4,5,6,7])=[[4],[2],[1,5,6],[3],[7]]
// @test([1,2,3,4,6,5,7])=[[4],[2],[1,5,6],[3],[7]]
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int,int,int>> list; // <col,row,val>
        function<void(TreeNode*,int,int)> dfs =
        [&](TreeNode*node,int col,int row){
            if(!node) return;
            list.emplace_back(col, row, node->val);
            if(node->left) dfs(node->left, col-1, row+1);
            if(node->right)dfs(node->right,col+1, row+1);
        };
        dfs(root, 0, 0);
        sort(list.begin(), list.end());
        vector<vector<int>> ans;
        int cur_col = INT_MIN;
        for(auto & [col, row, val] : list){
            if(cur_col != col){
                cur_col = col;
                ans.push_back({});
            }
            ans.back().emplace_back(val);
        }
        return ans;
    }
};